package com.wtgroup.demo.leetcode.q046_全排列;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Q046_LC2 {
    /**顺序保证
     *
     * 使用额外的对列放排列, 不改变原数组. 就避免了顺序改变问题.
     * 1) 存储单个结果容器;
     * 2) 记录被使用的数字.
     * 3) 大结果容器.
     * 4) 原数组(不可变).
     * 5) maxSize, 如果需要限制排列个数.
     */
    public List<List<Integer>> permute(int[] nums) {
        Deque<Integer> path = new ArrayDeque<>();
        List<List<Integer>> vessel = new ArrayList<>();
        // 下标->true|false
        boolean[] used = new boolean[nums.length];
        func(nums, path, used, vessel);

        return vessel;
    }

    private void func(int[] nums, Deque<Integer> path, boolean[] used, List<List<Integer>> vessel/*, int maxSize*/) {
        int n = nums.length;
        if (path.size()== n) {
            vessel.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < n; i++) {
            if(used[i]) continue;
            int num = nums[i];
            path.addLast(num);
            used[i] = true;
            func(nums, path, used, vessel/*, maxSize*/);
            path.removeLast();
            used[i] = false;
            // if (vessel.size()==maxSize) {
            //     return;
            // }
        }
    }
}
